#ifndef _SIMULATOR_HH_
#define _SIMULATOR_HH_
#include "State.h"
#include "Randomizer.hh"
#include <set>
#include "Bug.h"
#include "Map.hh"
#include "MapKnowledge.hh"


extern State state;
extern hive_estimator_t hive_est;
extern Map<unsigned> depth_map;
extern FastSet<unsigned> visited;
extern FastSet<unsigned> visited2;


/// exponential smoothing parameter
const double alpha = 0.5;


const double raze_bonus = 200;
const double raze_malus = 100;
const double lost_ant_malus = 1000;
const double new_ant_bonus = 50;
const double food_bonus = 50;
const double explo_bonus = 1;
const double view_bonus = 5;
const double enemies_view_bonus = 1;




struct Team
{
  signed tid;
  std::vector<uLocation> Ants;
  std::vector<uLocation> path;
  unsigned hive;
  double score;
  Map<double> expected_reward;

  double discounted_reward(double reward, unsigned step)
  {
    TRACK();

    return reward+reward/(step+1);
  }


  void init(signed _tid)
  {
    TRACK();
    ASSERT(torus.size);
    expected_reward.init();
    tid = _tid;
    hive = 0;
    score = 0;

    ASSERT(expected_reward._grid);

    for(Map<double>::iterator cell_it = expected_reward.begin();
	cell_it != expected_reward.end(); ++cell_it)
      *cell_it = explo_bonus + explo_bonus*(double)(rand()%10000)/10000.0;


  }


  void clear(void)
  {
    TRACK();
    Ants.clear();
    path.clear();
    score = 0;
    hive = 0;

    ASSERT(expected_reward._grid);
  }



  double eval_visibility(signed team, unsigned step, unsigned troops)
  {
    TRACK();
    Map<Square> & map(state.map);
    
    unsigned mytroops = 0;
    unsigned enemies = 0;
    unsigned invisible = 0;
    unsigned total = 1;
    visited2.reset();

    for(std::vector<uLocation>::const_iterator it = Ants.begin();
	it != Ants.end(); ++it)
      if(map.at(*it).ant == team)
	{
	  mytroops ++;

	  // push starting locations
	  std::queue<uLocation> locQueue;
	  visited.reset();

	  locQueue.push(*it);
	  depth_map[*it] = 0;
	  visited.insert(*it);
    
	  // spread around
	  while(!locQueue.empty())
	    {
	      uLocation cLoc = locQueue.front();
	      locQueue.pop();
	
	      if(not visited2.count(cLoc))
		{
		  visited2.insert(cLoc);
		  if(not map[cLoc].isVisible)
		    invisible++;
		  if(map[cLoc].ant != -1 and map[cLoc].ant!=team)
		    enemies++;
		  total++;
		}
	    
	      for(unsigned d=0; d<Torus::TDIRECTIONS; d++)
		{
		  uLocation nLoc = torus.getLocation(cLoc, d);
		  if(not visited.count(nLoc) and torus.distance(*it,nLoc)<=torus.viewRadius)
		    {
		      locQueue.push(nLoc);
		      depth_map[nLoc] = depth_map[cLoc]+1;
		      visited.insert(nLoc);
		    }
		}
	    }
	}

    return (view_bonus*invisible)/(double)total + (enemies_view_bonus*enemies)/(double)(1+troops-mytroops);

  }


  void attraction1(Map<double> & expected_reward, 
		  std::vector<uLocation>::const_iterator target_begin, 
		  std::vector<uLocation>::const_iterator target_end, 
		  unsigned maxdepth, unsigned mindepth, double w)
  {
    TRACK();
    ASSERT(expected_reward._grid);
    
    Map<Square> & map(state.map);

    
    // push starting locations
    std::queue<uLocation> locQueue;
    visited.reset();

    bug << "init expected reward for food " << std::endl;
    for(std::vector<uLocation>::const_iterator it = target_begin;
	it != target_end; ++it)
      {
	bug << ' ' << torus.to_str(*it);
	locQueue.push(*it);
	depth_map[*it] = 0;
	visited.insert(*it);
      }
    bug << std::endl;


    // spread around
    while(!locQueue.empty())
      {
	uLocation cLoc = locQueue.front();
	locQueue.pop();

	
	if(tid>0 and depth_map.at(cLoc)<3) bug << "Visiting : " << torus.to_str(cLoc) << std::endl;
	
	if(depth_map[cLoc]>mindepth)
	  expected_reward[cLoc] = 
	    0.75* expected_reward.at(cLoc) + 0.25*w/(1.0 + depth_map.at(cLoc) - mindepth);
	else
	  expected_reward[cLoc] =
	    0.75* expected_reward.at(cLoc) + 0.25*w;
	
	for(unsigned d=0; d!=Torus::TDIRECTIONS; d++)
	  {
	    uLocation nLoc = torus.getLocation(cLoc, d);
	    if(not visited.count(nLoc) and 
	       not map.at(nLoc).isWater and
	       map.at(nLoc).wasVisible
	       and depth_map[cLoc]<maxdepth)
	      {
		locQueue.push(nLoc);
		depth_map[nLoc] = depth_map[cLoc]+1;
		visited.insert(nLoc);
	      }
	  }
      }
  }



  void attraction(Map<double> & expected_reward, 
		  std::vector<Ant>::const_iterator target_begin, 
		  std::vector<Ant>::const_iterator target_end, 
		  unsigned maxdepth, unsigned mindepth, double w)
  {
    TRACK();
    ASSERT(expected_reward._grid);
    Map<Square> & map(state.map);


    
    // push starting locations
    std::queue<uLocation> locQueue;
    visited.reset();

    for(std::vector<Ant>::const_iterator it = target_begin;
	it != target_end; ++it)
      {
	locQueue.push(it->loc);
	depth_map[it->loc] = 0;
	visited.insert(it->loc);
      }
    
    // spread around
    while(!locQueue.empty())
      {
	uLocation cLoc = locQueue.front();
	locQueue.pop();
	
	
	if(depth_map[cLoc]>mindepth)
	  expected_reward[cLoc] = 
	    0.75* expected_reward[cLoc] + 0.25*w/(1.0 + depth_map[cLoc] - mindepth);
	else
	  expected_reward[cLoc] =
	    0.75* expected_reward[cLoc] + 0.25*w;
	
	for(unsigned d=0; d<Torus::TDIRECTIONS; d++)
	  {
	    uLocation nLoc = torus.getLocation(cLoc, d);
	    if(not visited.count(nLoc) and 
	       not map.at(nLoc).isWater and 
	       map.at(nLoc).wasVisited and
	       depth_map[cLoc]<maxdepth)
	      {
		locQueue.push(nLoc);
		depth_map[nLoc] = depth_map[cLoc]+1;
		visited.insert(nLoc);
	      }
	  }
      }
  }


    





  void prepare_simulation(void)
  {
    TRACK();
    ASSERT(expected_reward._grid);

    /*
    bug << "set water to zero" << std::endl;

    
    for(uLocation loc = 0; loc != torus.size; ++loc)
      {
	if(state.map[loc].isWater)
	  expected_reward.at(loc) = 0;
      }

    bug << "precompute potential" << std::endl;
    
    attraction1(expected_reward, state.food.begin(), state.food.end(),
		torus.viewRadius*10, 1, food_bonus);

    attraction(expected_reward, state.enemyHills.begin(), state.enemyHills.end(),
	       torus.viewRadius*10, 0, raze_bonus);
    */


  }



  void boost(signed t, double S)
  {
    if(Ants.empty()) return;

    ASSERT(expected_reward._grid);
    ASSERT(not Ants.empty());
    

    double relative_score = 3.0*score - S;

    double mix = alpha;
    for(unsigned v = 0; v!=path.size(); ++v)
      {
	if(v%Ants.size()==0) mix *= .5;
	expected_reward.at(path[v]) = 
	  (1-mix) * expected_reward.at(path[v]) +
	  mix * relative_score;
      }
      


#if 0
#ifdef DEBUG
    bug << "* show path of size " << path.size() << " for team " << t
	<< std::endl;

    for(std::vector<uLocation>::const_iterator cell_it = path.begin();
	cell_it != path.end(); ++cell_it)
      state.map[*cell_it].ant = t;

    bug << state << std::endl;
#endif
#endif
  }


  void explore(signed team, uLocation & loc, unsigned step)
  {
    TRACK();

    // list valid options
    std::vector<uLocation> options;
    for(unsigned d=0; d!=Torus::TDIRECTIONS; ++d)
      {
	uLocation nLoc = torus.getLocation(loc,d);
	if(state.map[nLoc].wasVisible 
	   and not state.map[nLoc].isWater 
	   and state.map[nLoc].ant == -1)
	  options.push_back(nLoc);
      }

    if(options.empty()) // no valid movement
      {
	if(state.map[loc].ant == -1) // stay
	  {
	    path.push_back(loc);
	    state.map.at(loc).ant = team;
	  }
	else // cannot stay!!
	  {
	    bug << "Ant collision at " << torus.to_str(loc) << std::endl;
	    score -= discounted_reward(2*lost_ant_malus,step);
	  }
      }
    else // move
      {
	uLocation nLoc = options[rand()%options.size()];
	path.push_back(nLoc);
	state.map.at(nLoc).ant = team;
	loc = nLoc;
      }
  }


  void exploit(signed team, uLocation & loc, unsigned step)
  {
    TRACK();

    // select best valid movement if exists
    double best = expected_reward[loc];
    uLocation best_option = loc;
    for(unsigned d=0; d!=Torus::TDIRECTIONS; ++d)
      {
	uLocation nLoc = torus.getLocation(loc,d);
	if(state.map[nLoc].wasVisible 
	   and not state.map[nLoc].isWater 
	   and state.map[nLoc].ant == -1)
	  {
	    if(expected_reward[nLoc]>best or (expected_reward[nLoc]==best and rand()%2==0)) 
	      {
		best = expected_reward[nLoc];
		best_option = nLoc;
	      }
	  }
      }

    if(state.map[best_option].ant != -1)
      {
	bug << "Ant collision at " << torus.to_str(loc) << std::endl;
	score -= discounted_reward(2*lost_ant_malus,step);
      }
    else
      {
	path.push_back(best_option);
	state.map.at(best_option).ant = team;
	loc = best_option;
      }
  }



    


  void make_random_moves(signed team, unsigned step, unsigned sim)
  {
    TRACK();
    ASSERT(expected_reward._grid);
    
    //random_shuffle(Ants.begin(),Ants.end());
  
    // remove old position and mark dead ants
    for(std::vector<uLocation>::const_iterator it = Ants.begin();
	it!=Ants.end(); ++it)
      {
	if(state.map.at(*it).ant == team)
	  {
	    state.map.at(*it).ant = -1;
	  }
	else
	  {
	    if(state.map.at(*it).ant != -1)
	      {
		bug << " at " << torus.to_str(*it) << " = " << state.map.at(*it).ant
		    << std::endl;
		ASSERT(state.map.at(*it).ant != -1);
	      }
	    state.map.at(*it).wasKilled = true;
	  }
      }
   
    // select randomly a new position for each living ant
    ASSERT(torus.size);
    for(std::vector<uLocation>::iterator it = Ants.begin();
	it!=Ants.end(); ++it)
      {
	if(not state.map.at(*it).wasKilled)
	  {
	    if(true) // exploration phase : random walk
	      explore(team,*it,step);
	    else // exploitation phase : best expected reward
	      exploit(team,*it,step);
	  }
	else
	  {
	    // remove the marks
	    state.map.at(*it).wasKilled = false;
	  }
      }
  }
  
};




struct Simulator
{
  std::vector<Team> teams;


  
  void init(void)
  {
    TRACK();
    ASSERT(torus.size);

    teams = std::vector<Team>(2,Team());
    for(signed t = 0; t<2; ++t)
      {
	teams[t].init(t);
      }
  }


  void init_simulations(void)
  {
    TRACK();

    for(unsigned t = 0; t<teams.size(); ++t)
      {
	bug << "prepare team " << t << std::endl;
	teams.at(t).prepare_simulation();
      }
  }

  

  void begin_simulation(void)
  {
    TRACK();

    for(unsigned t = 0; t<teams.size(); ++t)
      {
	teams.at(t).clear();
      }


    ASSERT(not teams.empty());

    teams.at(0).Ants.assign(state.myAnts.begin(),state.myAnts.end());
    //teams.at(0).path.assign(state.myAnts.begin(),state.myAnts.end());
    teams.at(0).hive = hive_est.hive;
    
    for(std::vector<Ant>::const_iterator ant_it = state.enemyAnts.begin();
	ant_it != state.enemyAnts.end(); ++ant_it)
      {
	unsigned t = ant_it->team;
	if(t >= teams.size()) 
	  {
	    bug << "New enemy team number: " << t << '/' << teams.size();
	    bug << " at Ant " << torus.to_str(ant_it->loc) 
		<< std::endl;
	    while(t>=teams.size())
	      {
		teams.push_back(Team());
		teams.back().init(teams.size()-1);
		ASSERT(teams.size()<20);
	      }
	  }
	
	teams.at(ant_it->team).Ants.push_back(ant_it->loc);
	//teams.at(ant_it->team).path.push_back(ant_it->loc);
      }

    for(std::vector<Ant>::const_iterator ant_it = state.enemyHills.begin();
	ant_it != state.enemyHills.end(); ++ant_it)
      {
	unsigned t = ant_it->team;
	if(t >= teams.size()) 
	  {
	    bug << "New enemy team number: " << t << '/' << teams.size();
	    bug << " at Hill " << torus.to_str(ant_it->loc) 
		<< std::endl;
	    while(t>=teams.size())
	      {
		teams.push_back(Team());
		teams.back().init(teams.size()-1);
		ASSERT(teams.size()<20);
	      }
	  }
      }

    
  }





  void life_and_death(unsigned step)
  {
    TRACK();

    // Resolve combat with wasKilled
    for(unsigned t =0; t!=teams.size(); ++t)
      if(not teams[t].Ants.empty())
	{
	  for(std::vector<uLocation>::iterator it = teams[t].Ants.begin();
	      it!=teams[t].Ants.end(); ++it)
	    if(state.map[*it].ant!=-1)
	      {
		if(will_die(state.map, *it, t))
		  {
		    state.map[*it].wasKilled = true;
		  }
	      }
	}

    // Remove Killed ants
    for(unsigned t =0; t!=teams.size(); ++t)
      if(not teams[t].Ants.empty())
	{
	  for(std::vector<uLocation>::iterator it = teams[t].Ants.begin();
	      it!=teams[t].Ants.end(); ++it)
	    {
	      if(state.map[*it].wasKilled)
		{
		  state.map[*it].ant = -1;
		  state.map[*it].wasKilled = false;
		  teams[t].score-= teams[t].discounted_reward(lost_ant_malus,step);
		  bug << "team " << t << " lost an Ant at " <<  torus.to_str(*it) << std::endl;
		}
	      // else if (not state.map[*it].isVisible)
	      // 	{
	      // 	  teams[t].score += explo_bonus/pow(step,0.1);
	      // 	}
	    }
	}
  }


  void eval_hills(unsigned step)
  {
    TRACK();

    for(std::vector<uLocation>::const_iterator it = state.myHills.begin(); 
	it!=state.myHills.end(); ++it)
      if(state.map[*it].isHill)
	{
	  ASSERT(state.map[*it].hillPlayer == 0);
	  bug << "my Hill at " << torus.to_str(*it) << std::endl;
	  if(state.map[*it].ant == -1 and teams[0].hive>0)
	    {
	      teams[0].Ants.push_back(*it);
	      state.map[*it].ant = (signed)0;
	      teams[0].hive--;
	      teams[0].score+= teams[0].discounted_reward(new_ant_bonus,step);
	      bug << "team " << 0 << " is proud to anounce a birth at " 
		  <<  torus.to_str(*it) << std::endl;
	    }
	  else if (state.map[*it].ant != -1 and state.map[*it].ant != 0)
	    {
	      signed enemy_team = state.map[*it].ant;
	      ASSERT(enemy_team<(signed)teams.size());
	      teams[state.map[*it].ant].score += 
		teams[enemy_team].discounted_reward(raze_bonus,step);

	      teams[0].score -= teams[0].discounted_reward(raze_malus,step);
	      bug << "team " << 0 << " lost an Hill at " <<  torus.to_str(*it) << std::endl;
	      state.map[*it].isHill = false;
	      state.map[*it].hillPlayer = -1;
	    }
	}


    for(std::vector<Ant>::const_iterator it = state.enemyHills.begin(); 
	it!=state.enemyHills.end(); ++it)
      if(state.map[it->loc].isHill)
	{
	  ASSERT(state.map[it->loc].hillPlayer == (signed)it->team);
	  bug << "enemy Hill at " << torus.to_str(it->loc) << std::endl;
	  if(state.map[it->loc].ant == -1 and teams[it->team].hive>0)
	    {
	      bug << "free Hill" << std::endl;
	      ASSERT(it->team<teams.size());
	      teams[it->team].Ants.push_back(it->loc);
	      state.map[it->loc].ant = (signed)it->team;
	      teams[it->team].hive--;
	      teams[it->team].score+= teams[it->team].discounted_reward(new_ant_bonus,step);
	      bug << "team " << it->team << " is proud to anounce a birth at " 
		  <<  torus.to_str(it->loc) << std::endl;
	    }
	  else if (state.map[it->loc].ant != -1 and state.map[it->loc].ant != (signed)it->team)
	    {
	      bug << "razed Hill" << std::endl;
	      signed enemy_team = state.map[it->loc].ant;
	      ASSERT(enemy_team<(signed)teams.size());
	      
	      teams[enemy_team].score += teams[enemy_team].discounted_reward(raze_bonus,step);
	      teams[it->team].score -= teams[it->team].discounted_reward(raze_malus,step);
	      bug << "team " << it->team << " lost an Hill at " <<  torus.to_str(it->loc) << std::endl;
	      state.map[it->loc].isHill = false;
	      state.map[it->loc].hillPlayer = -1;
	    }
	}

    
  }
    


  void eval_food(unsigned step)
  {
    TRACK();
    
    for(unsigned t = 0; t!=teams.size(); ++t)
      if(not teams[t].Ants.empty())
	{
	  for(std::vector<uLocation>::iterator it = state.food.begin();
	      it!=state.food.end(); ++it)
	    {
	      if(state.map[*it].isFood and this_food_is_for_me(state.map,*it,t))
		{
		  state.map[*it].isFood = false;
		  teams[t].hive++;
		  teams[t].score += teams[t].discounted_reward(food_bonus,step);
		  bug << "team " << t << " grabs some food at " <<  torus.to_str(*it) << std::endl;
		}
	    }
	}
  }


  void eval_visibility(unsigned step)
  {
    TRACK();
    
    unsigned troops = 0;
    for(unsigned team = 0; team!=teams.size(); ++team)
      {
	for(std::vector<uLocation>::const_iterator it = teams[team].Ants.begin();
	    it != teams[team].Ants.end(); ++it)
	  if(state.map.at(*it).ant == (signed)team) troops ++;
      }


    for(unsigned t = 0; t!=teams.size(); ++t)
      {
	double reward = teams[t].eval_visibility(t,step,troops);
	teams[t].score += teams[t].discounted_reward(reward,step);
      }
  }


  void eval_position(unsigned step)
  {
    TRACK();

    life_and_death(step);
    eval_hills(step);
    eval_food(step);
    eval_visibility(step);
  }


  
  void make_random_moves(unsigned nsup, unsigned sim)
  {
    TRACK();
    for(unsigned step=1; step<nsup; ++step)
      {
	for(unsigned team = 0; team!=teams.size(); ++team)
	  {
	    teams.at(team).make_random_moves(team,step,sim);
	  }
	eval_position(step);
      }
  }


  void end_simulation(void)
  {
    //TRACK();

    // core
    double S = 0;
    for(unsigned t = 0; t!=teams.size(); ++t)
      S += teams[t].score;


    
    
    for(unsigned t = 0; t!=teams.size(); ++t)
      if(not teams[t].Ants.empty() and fabs(2*teams[t].score - S)>.1)
	{
	  if(t==0 and fabs(2*teams[0].score - S)>0)
	    {
	      bug << "After simulation team " << t << " score is " << teams[t].score
		  << ", relative score is " << (3*teams[t].score - S)
		  << std::endl;
	      bug  << "after simulation map:" << std::endl;
	      bug << state << std::endl;
	    }

	  teams[t].boost(t,S);
	}
    

    state.restore();
  }
  

};










#endif /* _SIMULATOR_HH_ */
